package com.offer;

/**
 * @program: study
 * @className: ZeroOneBag
 * @description: TODO
 * @author: kukuxiahuni
 * @create: 2019-12-20 17:52
 * @version: v1.0
 **/
public class ZeroOneBag {

    private int maxWeight = Integer.MIN_VALUE;
    private int[] weight = {2, 2, 4, 6, 3};
    private int n = 5; //背包的最大容量
    private int w = 9; //背包可以装的最大值

    public static void main(String[] args) {
        ZeroOneBag zeroOneBag = new ZeroOneBag();
        zeroOneBag.f(0, 0);
        System.out.println(zeroOneBag.maxWeight);
    }

    /**
     * 功能描述: cw： 当前背包的重量
     *
     * @param:
     * @return:
     * @auther: kukuxiahuni
     * @date: 2019/12/20 5:54 下午
     * @modify_auther: kukuxiahuni
     * @modify_time: 2019/12/20 5:54 下午
     **/
    public void f(int i, int cw) {

        if (cw == w || i == n) {
            if (cw > maxWeight) {
                maxWeight = cw;
            }
            return;
        }


        /**
         *  放入i
         */
        if (cw + weight[i] <= w) {
            f(i + 1, cw + weight[i]);
        }

        /**
         * 不放入i
         */
        f(i + 1, cw);

    }
}
